package com.cat.binaryTree;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximum-sum-bst-in-binary-tree/
 * @create 2025/9/25 19:36
 * @since JDK17
 */

public class Solution61 {
    int ans;
    int[] dfs(TreeNode root) {
        if (root == null) { // key : 最小值，val : 最大值
            return new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE, 0, 1};
        }
        int[] l = dfs(root.left), r = dfs(root.right);
        int cur = root.val, min = Math.min(l[0], r[0]), max = Math.max(l[1], r[1]), sum = cur + l[2] + r[2], isLegal = l[3] + r[3];
        if (cur > l[1] && cur < r[0] && isLegal == 2) {
            ans = Math.max(ans, sum);
            isLegal = 1;
        } else {
            isLegal = 0;
        }
        return new int[]{Math.min(cur, min), Math.max(cur, max), sum, isLegal};
    }
    public int maxSumBST(TreeNode root) {
        dfs(root);
        return ans;
    }
}
